/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-10-10
 * Time:20:28
 */
/*
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1:

输入: 二叉树: [1,2,3,4]
       1
     /   \
    2     3
   /
  4

输出: "1(2(4))(3)"

解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。

 */

/*
class Solution{
     public void tree2strChild(TreeNode root,StringBuilder st){
         if(root == null){
             return;
         }
         st.append(root.val);

         //处理左树
         if(root.left == null){
            if(root.right == null){
                return;
            }else{
                st.append("()");
            }
         }else{
             st.append("(");
             tree2strChild(root.left,st);
             st.append(")");
         }
        //处理右树
         if(root.right == null){
            return;
         }else{
             st.append("(");
             tree2strChild(root.right,st);
             st.append(")");
         }
     }
        public String tree2str(TreeNode root){
            if(root == null){
                return null;
            }

            StringBuilder st = new StringBuilder();
            tree2strChild(root,st);
            return st.toString();
        }
 }
 */
    /*
        通过前序(后续)遍历 可以确定根节点
        在中序遍历的结果中 找到根节点所在的位置  根的左边是左树部分 根的右边是右树部分

        能否根据前序与后续构建二叉树？
        因为前序与后续只能确定根的位置，不能确定左树的值。
 */
    /*
    给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。

class Solution {


    public int preIndex = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin, int iend) {
        if(inbegin > iend){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findInorderIndex(inorder,inbegin,iend,root.val);
        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex - 1);
        root.right = buildTreeChild(preorder,inorder,rootIndex + 1,iend);

        return root;

    }

    public int findInorderIndex(int[] inorder,int inbegin,int iend,int key){
        for(int i = inbegin;i <= iend; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    // 每次遍历到前序遍历的某个几点后，在中序中找到这个数的下标
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null){
            return null;
        }
        return buildTreeChild(preorder,inorder,0,inorder.length - 1);
    }
}
     */
    /*
    根据一棵树的中序遍历与后序遍历构造二叉树
     */
    /*
    class Solution {
    public int postIndex = 0;
    public  TreeNode buildTreeChild(int[] inorder,int[] postorder,int ibegin,int iend){
        if(ibegin>iend){
            return null;
        }
        if(inorder == null || postorder == null) return null;

        TreeNode root  = new TreeNode(postorder[postIndex]);
        int rootIndex = findRootIndex(inorder,ibegin,iend,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder,postorder,rootIndex+1, iend);
        root.left = buildTreeChild(inorder,postorder,ibegin,rootIndex -1);

        return root;
    }

    public  int findRootIndex(int[] inorder, int ibegin,int iend, int key){
        int i = 0;
        for(i = ibegin; i<= iend;i++ ){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || inorder == null) return null;
        postIndex = postorder.length - 1 ;
        return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
    }
     */


    /*
    平衡二叉树




    class Solution {
    public int TreeDepth(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftDepth = TreeDepth(root.left);
        int rightDepth = TreeDepth(root.right);

        if(leftDepth > rightDepth){
            return leftDepth + 1;
        }else{
            return rightDepth + 1;
        }
    }
    public boolean check(TreeNode root){
        if(root == null){
            return true;
        }
        int leftDepth= TreeDepth(root.left);
        int rightDepth = TreeDepth(root.right);

        if(leftDepth + 1 == rightDepth){
             return true;
         }else if(leftDepth  == rightDepth + 1){
             return true;
         }else if(leftDepth == rightDepth){
             return true;
         }else{
             return false;
         }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }

        return  check(root) && isBalanced(root.left) && isBalanced(root.right);
    }
}
     */
public class TesrDemo {

}
